1. Field of the Invention
The invention relates generally to the design of hardware electronic circuits using hardware design language (HDL) descriptions of circuit behavior, and more specifically, to the extraction of hardware circuit components from control data flow graph (CDFG) structure produced from HDL descriptions to hardware circuit behavior.
2. Description of the Related Art
Simulation has made it possible to design electronic circuits and systems in terms of system behavior. Simulation at various levels (physical, RTL, behavioral, etc.) has made it possible for many designers to try out various circuit design possibilities and prototypes without actually fabricating designs. It also has aided designers in identifying various bugs before the circuit is manufactured. Simulation also has made it easier to develop and test a partial circuit or system design since one need not develop an implementation of the whole design before it can be simulated. In addition, behavioral descriptions of circuits or systems can make it easier to simulate abstractions of designs/environments.
Hardware Design Languages (HDLs), enable hardware designers to design hardware circuits in essentially the same manner in which they write software programs. Many existing hardware designs have been written in HDLs like Verilog 2 and VHDL, for example. The IEEE Standard VHDL Language Reference Manual, Institute of Electrical and Electronics Engineers, 1988 explains the VHDL language and its origin. Donald E. Thomas and Philip R. Moorby, The Verilog Hardware Description Language, Kluwer Academic Publishers, Nowell, Mass., 1991 describe the Verilog language.
Basically, HDL descriptions do not describe circuit or system components directly. Instead, they describe the behavior of components. These HDLs are in essence programming languages used to describe massively parallel computations (systems of parallel sequential processes). They are designed for simulation, and their semantics are defined in terms of simulation results. To automate the design process as fully as possible and ensure design consistency, it is desirable to extract circuits directly from these HDL programs. The term extract as used herein includes automated processes that run on a computer system and translate a HDL description of circuit behavior into a hardware circuit that exhibits the described behavior. A circuit may be extracted, for instance, through algorithmic processes that map portions of a hardware description to corresponding portions of a hardware circuit. Unfortunately, the complex process of circuit extraction may be further complicated from time to time, for example, by the possibility of mismatches between the underlying models for HDLs and the actual hardware circuits.
Theoretically and most intuitively, to extract circuits from a system of parallel sequential processes specified using an HDL, one may conduct exhaustive simulation and map the simulation traces directly into circuit components. Due to the enormous number of possible inputs to a complex system, however, such an exhaustive simulation approach often is likely to require so much computation and so much time as to be impractical.
In general, there can be a substantial variation between the semantic models of input HDLs and the synthesized target hardware architectures. A canonical intermediate representation of a HDL behavioral description often is employed to preserve the original behavior of the input HDL specification, while allowing the addition of synthesis results through various bindings, optimizations and mappings. A flow graph is a well known type of intermediate information structure that can represent the flow of control and/or data in a HDL behavioral description.
A control data flow graph (CDFG) is one example of a type of flow graph that can serve as an intermediate representation of the interaction between the control path and data path of processes of a HDL behavioral description. A control-flow portion of a CDFG captures sequencing, conditional branching and looping constructs in a behavioral description, while the data-flow graph portion captures operational activity typically described by assignment statements of a HDL description. The use of CDFGs in high-level synthesis of hardware circuits is well known. See, Robert A. Walker, xe2x80x9cA Survey of High-Level Synthesis Systemsxe2x80x9d, in Research Report No. CMUCAD8935, SRCCMU Research Center for Computer-Aided Design, Carnegie Mellon University, Pittsburgh, Pa. 152133890, June 1989, for a discussion of the use of CDFGs in high-level synthesis.
The construction of a flow graph or more specifically, a CDFG, from a source program can be achieved, for example, by traversing a parse-tree of a source program. Consider the following sample Verilog fragment,
if (c1)
d=x;
if (c2)
d=y;
The CDFG of FIG. 1 can be produced by parsing the above Verilog fragment. It will be appreciated that Verilog is just one example of a HDL. A thorough explanation of the construction of a flow graph from a source program is provided, for example, in Alfred V. Aho, Ravi Sethi, and Jeffrey D Ullma, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1985, and in Charles N. Fischer Jr. and Richard J. Le Blanc, Crafting a Compiler, The Benjamin/Cumings Publishing Company, Menlo Park, Calif., 1988.
U.S. Pat. No. 5,530,841 and U.S. Pat. No. 5,581,781, both issued to Gregory et al., describe earlier techniques to extract sequential circuits by using HDLs to produce control flow graphs (CFGs) and by then matching the CFGs to hardware circuits. A sequential circuit is a circuit whose outputs are functions of its inputs as well as its current state. A sequential circuit typically includes a sequential state storage device such as a flip-flop or a latch, for example. Basically, the sequential circuit extraction process disclosed by Gregory et al. involved an analysis of a CFG to determine what hardware circuit to extract from a portion of the CFG.
Szu-Tsung Cheng, Robert K. Brayton, Gary York, Katherine Yelick, and Alexander Saldanha, xe2x80x9cCompiling Verilog into Timed Finite State Machinesxe2x80x9d, International Verilog Conference, 1995, and Szu-Tsung Cheng and Robert K. Brayton, xe2x80x9cCompiling Verilog into Automataxe2x80x9d, Memorandum UCB/ERL M94/37, University of California at Berkeley, 1994, describe an earlier alternative approach to modeling a wide range of HDL programs. Basically, this alternative approach attempts to use two primitive logic devices, edgedetector and resolution logic, to synchronize different processes described using a HDL. An advantage of this earlier alternative approach is that it can model a very large subset of processes described using a HDL. It can even model processes that do not have actual hardware implementations. A weakness of this earlier alternative approach is that its primitive logic devices often do not afford easy hardware mapping.
While earlier techniques for extracting sequential circuits from HDL behavioral descriptions generally have been successful, there have been some shortcomings. Style guides have been developed in order to facilitate the extraction of hardware circuit information from HDL descriptions. A style guide instructs the creator of the HDL description as to the manner or xe2x80x9cstylexe2x80x9d in which HDL descriptions are to be written in order to ensure accurate extraction of circuit information. Thus, style guides may serve to limit the manner in which HDL descriptions may be expressed so as to ensure accurate interpretation of an HDL description. xe2x80x9cSynopsys HDL Coding Style: Synthesisxe2x80x9d, by Snyopsys, 1998 is one example of such a style guide.
Thus, there has been a need for improvement in the extraction of state storage devices from HDL behavioral descriptions. More specifically, there has been a need for improvement in the use of control flow data graphs (CDFGs) to extract sequential hardware devices from HDL statements. Furthermore, there has been a need for more flexibility in the styles that can be employed to create HDL descriptions. The present invention meets these needs.
In one aspect, the present invention may improve upon the ability to more accurately identify the need for latch, flip-flop and combinational logic circuits based upon a control data flow graph (CDFG) representation of a HDL description.
In another aspect, the present invention may provide wider latitude in the range of HDL styles that can be translated accurately into hardware circuits through the use of CDFGs.
In one aspect, the present invention provides a graph structure in a computer readable storage medium, produced from a CDFG representing an HDL description. The graph structure includes a path origination node and a path destination node and respective complete paths between the path origination node and the path destination node. Each respective complete path is associated with respective control statements.
In another aspect of the invention, respective complete paths of the graph information are traversed to determine whether there is a respective path that is not associated with a respective control statement.